\chapter{Шаблоны C++}

\section{Лекция 7.02.2012. Введение в шаблоны.}

\paragraph{Задача:} создать класс ArrayDouble для хранения double, после этого появилась необходимость создать класс для хранения Int: ArrayInt, при этом возникают
следующие проблемы:
	- дублирование кода (ясно что классы очень похожи)
	- поддержание нескольких версий (через некоторое время классы начнут жить отдельно друг от друга, с отдельными функциями и различными багами)
	
\paragraph{Подходы к решению}

\begin{itemize}	
\item Решение задача C style: Макросы:
\begin{lstlisting}
#define DefineArray(type, name) \\
	struct array##name {	\\
		type *data;	\\
		size_t size	\\
	};			\\
\end{lstlisting}
	
Какие проблемы возникают в этом случае? Главная проблема - отладка, препроцессор ничего не знает о C++, поэтому отлаживать нетривиальные проблемы очень трудно,
отсутствует проверка типов.


\item Решение ООП style: все хранимые объекты являются экземплярами класса наследника одного общего класса (Object, как, например, в Java).

\begin{lstlisting}
struct Array {
	Object *data;
	size_t size;
};
\end{lstlisting}

Какие проблемы, для хранения элементарных типов приходится создавать классы обертки, унаследованные от Object.
\end{itemize}

\paragraph{Задача:} теперь рассмотрим следующий пример: требуется реализовать функцию реализующий некоторый алгоритм, например, reverse (пересатвляем элементы массива):

\paragraph{Подходы к решению}

\begin{itemize}
\item 
\begin{lstlisting}
void reverse(int *array, size_t size);
\end{lstlisting}

придется опять поддерживать несколько версий со всеми вытекающими последствиями (см. выше)

\item
\begin{lstlisting}
#define ...
\end{lstlisting}

опять же, сложность отладки (см. выше)

\item
\begin{lstlisting}
void reverse(Object *array, size_t size);
\end{lstlisting}

трудности со встроенными типами (см. выше)

\item old school c-style:
\begin{lstlisting}
void reverse(void *data, size_t count, size_t element_size);
\end{lstlisting}

работаем с блоками памяти по element\_size байт, не опираясь на типы, что, очевидно, небезопасно
относительно типов, хотя в c библиотеках такие алгоритмы активно используются.
\end{itemize}

\paragraph{Как решать все эти проблемы в C++?} Решением является механизм шаблонов, код параметризуется некоторым параметром (для решения описанных выше задач типовым
параметром):

\begin{lstlisting}
template <class T>
struct Array {
	T *data;
	size_t size;
};
\end{lstlisting}

где T - типовой параметр (вместо T можно исользовать и другой идентификатор), кроме того вместо слова class можем использовать ключевое слово typename, в
данном контексте оба слова не различимы. Аналогичным образом параметризуются функции.

\paragraph{Относительно шаблонов есть следующие замечания:}

\begin{itemize}
\item сам шаблонный код не компилируется ни в какой объектный код

\item правильность кода шаблона проверяется очень поверхностно (на уровне синтаксиса, почти без семантики)
\end{itemize}
	
Реальная генерация кода и проверка корректности начинается после инстанцирования шаблона, т. е. подстановки типа вместо параметра Array<double>, сам шаблон
не начнет использоваться до тех пор, пока не будет создан объект шаблонного класса (или вызвана шаблонная функция), более того, т. к. инстанцирование шаблона
происходит лениво, то функция класса не будет скомпилирована пока она не будет вызвана, т. е. ошибку в функции вы не обнаружите, пока не вызовите ее.

\paragraph{Явное указание на компиляцию шаблона:}

\begin{lstlisting}
template Array<int>;
\end{lstlisting}

такая строка позволяет скомпилировать шаблон без создания объектов, и скомпилирует все методы класса.

Т. к. все генерация кода по шаблону происходит в момент встречи экземпляра (это некоторое упрощение, но не большое), то к моменту создания объекта, вызову функции
и т. д. определение шаблона должно быть полностью известно компилятору - вывод, шаблонам место в заголовочных файлах.

\paragraph{Пример разделения объявления и определения для шаблона:}

\begin{lstlisting}
//def.h
template <class T>
struct Array {
	T *data;
	size_t size;
	
	void clear();
};

#include "impl.h"
\end{lstlisting}

\begin{lstlisting}
//impl.h
template <class T>
void Array<T>::clear() {...}
\end{lstlisting}

но при этом, всеравно, место и определению и реализации шаблонов в заголовочных файлах.

\paragraph{Примечания:}

\begin{itemize}
\item все шаблонные методы являются inline по умолчанию, поэтому писать это слово не надо.

\item каждый инстанс шаблона является самостоятельным классом (в отличие, например, от ООП подхода с одним базовым классом)
\end{itemize}


\paragraph{Особенности использования шаблонных функций.}

\begin{lstlisting}
template <class T>
void sort(T *array, size_t size) {
	...
	if (m[i] < m[j]) // (1)
	...
}
\end{lstlisting}

(1) сработает только для тех типов, для которых оператор < имеет значение.

Вызов такой функции можно производить следующим образом:

\begin{lstlisting}
int p[] = {1, ..., 10};
size_t size = sizeof(p);

sort<int>(p, size);
\end{lstlisting}

Очевидно, что указание на int в данном случае избыточно, компилятор может сам угадать этот параметр (deducing), поэтому можно опускать эту спецификацию, поэтому
можно вызывать эту функцию и так:

\begin{lstlisting}
sort(p, size);
\end{lstlisting}

Шаблоны могут иметь несколько параметров, в этом случае могут возникать проблемы с угадыванием, кроме того, если сама функция имеет несколько параметров, то
могут возникать казусы:

\begin{lstlisting}
template <class T>
void swap(T &a, T &b) {
	...
}
\end{lstlisting}

если вызвать эту функцию так:

\begin{lstlisting}
int a = ...;
double b = ...;
swap(a, b);
\end{lstlisting}

возникает, очевидно, проблема.

Параметрами шаблонов могут быть не только типы, но и другие шаблоны или даже выражения типа int size. Возможности по угадыванию типов для шаблонов достаточно
широки, но магии не бывает, так что не забывайте, что такие ситуации возможны.

Шаблонные функции в случае перегрузки имеют наименьший приоритет, т. е. если не подошла ни одна нешаблонная функция, то вызывается шаблонная, кроме того шаблоны
генерируют функции с точным совпадением по типам, по этому все функции, в которых для вызова используется приведение типов будут использованы, только если нет
подходящей по "сигнатуре" шаблонной функции (естественно, все это работает только для параметризованного параметра).


\paragraph{Примеры шаблонных методов внутри шаблонного класса:}

\begin{lstlisting}
template <class T>
struct Array {
	template <class V> //(1)
	Array(Array<V> const &array) : data(new T[array.size()]), size(array.size()) {
		for (size_t i = 0; i < size; i++)
			data[i] = array.data(i);
	}
};
\end{lstlisting}

строку (1) можно вынести за пределы класса:

\begin{lstlisting}
template <class T>
template <class V>
struct Array {
	Array(Array<V> const &array) : data(new T[array.size()]), size(array.size()) {
		for (size_t i = 0; i < size; i++)
			data[i] = array.data(i);
	}
};
\end{lstlisting}

\paragraph{Примечания:}

\begin{itemize}
\item данный пример работает, если V не приводимо к T

\item шаблоны с различными параметрами - разные классы, поэтому мы используем функции array.size() и array.data(i)

\item конструктор копирования не может быть шаблонным (как деструктор, оператор присваивания и конструктор по умолчанию)
\end{itemize}